package com.sicheng.蓝桥.练习题.dp.二维费用的背包问题;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/9 22:33
 */
public class 零一背包 {
    /**
     * 题目描述
     * 有 n 件物品 和 一个容量为 V 的背包，背包最大承重是 M
     * 每件物品只能 用一次，第 i 件物品的 体积 是 vi，重量 是 mi，价值 是 wi
     * 求解一个选物品的 方案，使得 总体积 不超过 V，总重量 不超过 M 的，且 总价值 最大
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] dp = new int[v + 1][m + 1];
        int[][] bags = new int[n][3];
        for (int i = 0; i < n; i++) {
            bags[i][0] = scanner.nextInt();//v
            bags[i][1] = scanner.nextInt();//m
            bags[i][2] = scanner.nextInt();//w
        }


        for (int i = 0; i < n; i++) {
            for (int j = v; j >= bags[i][0]; j--) {
                for (int k = m; k >= bags[i][1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - bags[i][0]][k - bags[i][1]] + bags[i][2]);
                }
            }
        }

    }
}
